class Solution {
public:
    int MaxArea(const vector<int>& height) {
		if (height.size() == 0) {
			return 0;
		}
		int n = height.size();
		vector<int> left(n);
		vector<int> right(n);
		stack<int> stk;

		for (int i = 0; i < n; ++i) {
			if (i == 0) {
				left[i] = i;
			} else {
				while (!stk.empty() && height[stk.top()] >= height[i]) {
					stk.pop();
				}
				left[i] = (stk.empty() ? 0 : stk.top() + 1);
			}
			stk.push(i);
		}

		while (!stk.empty()) {
			stk.pop();
		}
		for (int i = n - 1; i >= 0; --i) {
			if (i == n - 1) {
				right[i] = i;
			} else {
				while (!stk.empty() && height[stk.top()] >= height[i]) {
					stk.pop();
				}
				right[i] = (stk.empty() ? n - 1 : stk.top() - 1);
			}
			stk.push(i);
		}

		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans = std::max(ans, height[i] * (right[i] - left[i] + 1));
		}
		return ans;
	}

	int maximalRectangle(vector<vector<char> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if (matrix.size() == 0 || matrix[0].size() == 0) {
			return 0;
		}
		int n = matrix.size();
		int m = matrix[0].size();
		vector<int> height(m);

		int ans = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (matrix[i][j] == '0') {
					height[j] = 0;
				} else {
					++height[j];
				}
			}
			ans = max(ans, MaxArea(height));
		}
		return ans;
	}

};